{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distinct Prime Factors of Product of Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctPrimeFactors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组乘积中的不同质因数数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>nums</code> ，对 <code>nums</code> 所有元素求积之后，找出并返回乘积中 <strong>不同质因数</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>质数</strong> 是指大于 <code>1</code> 且仅能被 <code>1</code> 及自身整除的数字。</li>\n",
    "\t<li>如果 <code>val2 / val1</code> 是一个整数，则整数 <code>val1</code> 是另一个整数 <code>val2</code> 的一个因数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,4,3,7,10,6]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 2<sup>5</sup> * 3<sup>2</sup> * 5 * 7 。\n",
    "共有 4 个不同的质因数，所以返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,4,8,16]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 2<sup>10</sup> 。\n",
    "共有 1 个不同的质因数，所以返回 1 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distinct-prime-factors-of-product-of-array](https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distinct-prime-factors-of-product-of-array](https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,3,7,10,6]', '[2,4,8,16]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        result = set()\n",
    "        for item in nums:\n",
    "            i = 2\n",
    "            while i * i <= item:\n",
    "                if item % i == 0:\n",
    "                    while item % i == 0:\n",
    "                        item /= i\n",
    "                    result.add(i)\n",
    "                i += 1\n",
    "            if item > 1:\n",
    "                result.add(item)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            res.extend(self.getdis(i))\n",
    "        return len(set(res))\n",
    "    \n",
    "    def getdis(self, n:int)->List[int]:\n",
    "        for i in range(2,int(n**0.5)+1):\n",
    "            if n % i == 0:\n",
    "                return [i] + self.getdis(n//i)\n",
    "        return [n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "        TotalFactors=[]\n",
    "        for j in range(len(nums)):\n",
    "            q=prime_factors(nums[j])\n",
    "            TotalFactors.extend(q)\n",
    "\n",
    "        return len(set(TotalFactors))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        mul = 1\n",
    "        for i in nums:\n",
    "            mul *= i\n",
    "        return len(Counter(self.get_factor_list(mul)))\n",
    "\n",
    "    def get_factor_list(self, num: int) -> List:\n",
    "        res = []\n",
    "        i = 2\n",
    "        while num > 1:\n",
    "            if num % i == 0:\n",
    "                res.append(i)\n",
    "                num //= i\n",
    "            else:\n",
    "                i += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        cur = []\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return \n",
    "            if n == 2:\n",
    "                cur.append(2)\n",
    "                return \n",
    "            for i in range(2,n+1):\n",
    "                if n % i == 0:\n",
    "                    cur.append(i)\n",
    "                    dfs(n // i)\n",
    "                    return \n",
    "        \n",
    "        for f in nums:\n",
    "            dfs(f)\n",
    "        return len(set(cur))\n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        def get_num_factors(num):\n",
    "            res, tmp = [], 2\n",
    "            if num == tmp:\n",
    "                return [num]\n",
    "            else:\n",
    "                while num >= tmp:\n",
    "                    if num % tmp == 0:\n",
    "                        res.append(tmp)\n",
    "                        num = num // tmp\n",
    "                        # print(num)\n",
    "                    else:\n",
    "                        tmp += 1\n",
    "            return res\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans *= num\n",
    "        res = get_num_factors(ans)\n",
    "        return len(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans=set()\n",
    "        for i in nums:\n",
    "            divisor = 2\n",
    "            while i > 1:\n",
    "                while i % divisor == 0:\n",
    "                    ans.add(divisor)\n",
    "                    i //= divisor\n",
    "                divisor += 1\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        l = set(map(int, '2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997'.split(',')))\n",
    "        ans = set()\n",
    "        for n in nums:\n",
    "            for i in l:\n",
    "                if n%i == 0: ans.add(i)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        def prime_factors(n):\n",
    "            factors = set()\n",
    "            d = 2\n",
    "            while d * d <= n:\n",
    "                if n % d == 0:\n",
    "                    factors.add(d)\n",
    "                    while n % d == 0:\n",
    "                        n //= d\n",
    "                d += 1\n",
    "            if n > 1:\n",
    "                factors.add(n)\n",
    "            return factors\n",
    "\n",
    "        distinct_factors = set()\n",
    "        for num in nums:\n",
    "            distinct_factors.update(prime_factors(num))\n",
    "\n",
    "        return len(distinct_factors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        # 思路：找出nums数组中的质数，把不是质数的分解为几个质数的乘积(递归)\n",
    "        def decompose(x):\n",
    "            # 分解一个数为两个数的乘积\n",
    "            for i in range(2,x):\n",
    "                if x%i==0:\n",
    "                    x=x//i\n",
    "                    break\n",
    "            return i,x\n",
    "            \n",
    "        \n",
    "        def not_prime(x):\n",
    "            # True不是质数，False是质数\n",
    "            for i in range(2,x):\n",
    "                if x%i==0:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        factors=[]\n",
    "        for num in nums:\n",
    "            if not not_prime(num):\n",
    "                factors.append(num)\n",
    "            else:\n",
    "                while not_prime(num):\n",
    "                    i,num=decompose(num)\n",
    "                    factors.append(i)\n",
    "                factors.append(num)\n",
    "        print(factors)\n",
    "        return len(set(factors))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]\n",
    "        ans = set()\n",
    "        nums = set(nums)\n",
    "        for num in nums:\n",
    "            for p in primes:\n",
    "                if num % p != 0:\n",
    "                    continue\n",
    "                ans.add(p)\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "            if num > 1:\n",
    "                ans.add(num)\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s=set()\n",
    "        for x in nums:\n",
    "            i =2\n",
    "            while i * i<=x:\n",
    "                if x%i==0:\n",
    "                    s.add(i)\n",
    "                    x//=i\n",
    "                    while x%i==0:\n",
    "                        x//=i\n",
    "                i+=1\n",
    "            if x> 1:\n",
    "                s.add(x)\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        g = defaultdict(int)\n",
    "        for n in nums:\n",
    "            d = 2\n",
    "            while n > 1:\n",
    "                if n % d == 0:\n",
    "                    g[d] += 1\n",
    "                    while n % d == 0:\n",
    "                        n //= d  \n",
    "                d += 1\n",
    "      \n",
    "        return len(g.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            for i in range(2,num+1):\n",
    "                if num%i == 0:\n",
    "                    a.add(i)\n",
    "                    num //= i\n",
    "                while num%i == 0:\n",
    "                    num //= i\n",
    "        # print(a)\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        visited_num = defaultdict(int)\n",
    "        def divide(num):\n",
    "            for i in range(2, num):\n",
    "                if num % i == 0:\n",
    "                    return divide(i) + divide(num // i)\n",
    "            return [num]\n",
    "        \n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            a.update(divide(num))\n",
    "        return len(a)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    s.add(i)\n",
    "                    x //= i \n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                 s.add(x)\n",
    "        return len(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                while x % i == 0:\n",
    "                    ans.add(i)\n",
    "                    x //= i \n",
    "                i += 1\n",
    "            if x > 1: ans.add(x)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "\n",
    "        def primesMarks(n):\n",
    "            #返回一个字典，表示2到n的所有素数\n",
    "            primes = {}\n",
    "            v = [0 for _ in range(n+1)]\n",
    "\n",
    "            for i in range(2, n+1):\n",
    "                if not v[i]:\n",
    "                    v[i] = i\n",
    "                    primes[i] = True\n",
    "                \n",
    "                for prime, _ in primes.items():\n",
    "                    if prime > v[i] or prime * i > n:\n",
    "                        break\n",
    "                    \n",
    "                    v[prime*i] = prime\n",
    "            \n",
    "            return primes\n",
    "\n",
    "        ans = 0\n",
    "        maxItem = max(nums)\n",
    "        primes = primesMarks(maxItem)\n",
    "\n",
    "        for num in nums:\n",
    "            if not len(primes):\n",
    "                return ans\n",
    "            \n",
    "            #num本身就是素数\n",
    "            if num in primes and primes[num]:\n",
    "                ans += 1\n",
    "                primes[num] = False\n",
    "                continue\n",
    "\n",
    "            #查询num的素因子\n",
    "            for prime, _ in primes.items():\n",
    "                if not num % prime and primes[prime]:\n",
    "                    ans += 1\n",
    "                    primes[prime] = False\n",
    "                \n",
    "                if prime > num:\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        res = set()\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            if j > 0 and x == nums[j-1]:\n",
    "                continue\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if  x % i == 0:\n",
    "                    res.add(i)\n",
    "                    x /= i\n",
    "                    while x % i == 0:\n",
    "                        x /= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                res.add(x)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for n in nums:\n",
    "            i = 2\n",
    "            while n >= i:\n",
    "                while n % i == 0:\n",
    "                    s.add(i)\n",
    "                    n //= i\n",
    "                i += 1\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    ans.add(i)\n",
    "                    x //= i \n",
    "                    while x % i == 0:\n",
    "                        x //= i \n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                ans.add(x)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        stat=True\n",
    "        ret=set()\n",
    "        for item in nums:\n",
    "            if stat and item%2==0 :\n",
    "                stat=False\n",
    "            while item%2==0: item//=2\n",
    "            for i in range(3,int(sqrt(item))+1,2):\n",
    "                if item%i==0:\n",
    "                    while item%i==0: item//=i\n",
    "                    ret.add(i)\n",
    "            if item>1: ret.add(item)\n",
    "        return len(ret)+(0 if stat else 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        a = dict()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            n = num\n",
    "            i = 2\n",
    "            while i <= n:\n",
    "                if i == n:\n",
    "                    if i not in a:\n",
    "                        res += 1\n",
    "                        a[i] = 1\n",
    "                    break\n",
    "                elif n % i == 0:\n",
    "                    if i not in a:\n",
    "                        res += 1\n",
    "                        a[i] = 1\n",
    "                    n = int(n / i)\n",
    "                else:\n",
    "                    i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while num >= i:\n",
    "                if num%i == 0:\n",
    "                    a.add(i)\n",
    "                    num //= i\n",
    "                while num%i == 0:\n",
    "                    num //= i\n",
    "                i += 1\n",
    "        # print(a)\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        MAXN = max(nums) + 1\n",
    "        prime = [False] * MAXN\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            if x in visited:\n",
    "                continue\n",
    "            visited.add(x)\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    if not prime[i]:\n",
    "                        prime[i] = True\n",
    "                        ans += 1\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1 and not prime[x]:\n",
    "                prime[x] = True\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    s.add(i)\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s.add(x)\n",
    "        return len(s)\n",
    "'''\n",
    "作者：灵茶山艾府\n",
    "链接：https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array/solutions/2040069/fen-jie-zhi-yin-shu-by-endlesscheng-x3kz/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        MAXN = max(nums) + 1\n",
    "        prime = [False] * MAXN\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    if not prime[i]:\n",
    "                        prime[i] = True\n",
    "                        ans += 1\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1 and not prime[x]:\n",
    "                prime[x] = True\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        prod = self.listProduct(nums)\n",
    "        factors = set()\n",
    "        i = 2\n",
    "        while i * i <= prod:\n",
    "            if prod % i == 0:\n",
    "                factors.add(i)\n",
    "                while prod % i == 0:\n",
    "                    prod //= i\n",
    "            i += 1\n",
    "        if prod > 1:\n",
    "            factors.add(prod)\n",
    "        return len(factors)\n",
    "\n",
    "    def listProduct(self, nums: List[int]) -> int:\n",
    "        product = 1\n",
    "        for num in nums:\n",
    "            product *= num\n",
    "        return product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "      prime = set()\n",
    "      for num in nums:\n",
    "        i = 2\n",
    "        while i * i <= num:\n",
    "          if num % i == 0:\n",
    "            prime.add(i)\n",
    "            num //= i\n",
    "            while num % i == 0:\n",
    "              num //= i\n",
    "          i += 1\n",
    "        if num > 1:\n",
    "          prime.add(num)\n",
    "      return len(prime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        res = set()\n",
    "        for n in nums:\n",
    "            i = 2\n",
    "            while i **2 <= n:\n",
    "                if n % i == 0:\n",
    "                    res.add(i)\n",
    "                    n //= i\n",
    "                    while n % i == 0:\n",
    "                        n //= i\n",
    "                i += 1\n",
    "            if n > 1:\n",
    "                res.add(n)\n",
    "        return len(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def prime_table():\n",
    "    n = 1001\n",
    "    is_prim = [True] * n\n",
    "    ans = deque()\n",
    "    i = 2\n",
    "    while i * i < n:\n",
    "        if is_prim[i]:\n",
    "            for j in range(i*i, n, i):\n",
    "                is_prim[j] = False\n",
    "        i += 1\n",
    "    for i in range(2, n):\n",
    "        if is_prim[i]:\n",
    "            ans.append(i)\n",
    "    return list(ans)\n",
    "\n",
    "Z = prime_table()\n",
    "Zs = set(Z)\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for num in nums:\n",
    "            if num in Zs:\n",
    "                ans.add(num)\n",
    "            else:\n",
    "                for z in Z:\n",
    "                    if z > num:\n",
    "                        break\n",
    "                    while num % z == 0:\n",
    "                        num //= z\n",
    "                        ans.add(z)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        visited_num = defaultdict(int)\n",
    "        def divide(num):\n",
    "            for i in range(2, num):\n",
    "                if num % i == 0:\n",
    "                    return divide(i) + divide(num // i)\n",
    "            return [num]\n",
    "        \n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            a.update(divide(num))\n",
    "        return len(a)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        def zhiyinshu(num):\n",
    "            r = set()\n",
    "            divisor = 2\n",
    "            while num > 1:\n",
    "                while num % divisor == 0:\n",
    "                    r.add(divisor)\n",
    "                    num //= divisor\n",
    "                divisor += 1\n",
    "\n",
    "            return r\n",
    "\n",
    "        results = set()\n",
    "        for num in nums:\n",
    "            r = zhiyinshu(num)\n",
    "            for j in r:\n",
    "                results.add(j)\n",
    "        # print(results)\n",
    "\n",
    "        return len(results) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        Prime_dic = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    Prime_dic.add(i)\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                Prime_dic.add(x)\n",
    "        return len(Prime_dic)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if 0 == x % i:\n",
    "                    s.add(i)\n",
    "                    while 0 == x % i:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1: s.add(x)\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        MAXN = max(nums) + 1\n",
    "        prime = [False] * MAXN\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    if not prime[i]:\n",
    "                        prime[i] = True\n",
    "                        ans += 1\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1 and not prime[x]:\n",
    "                prime[x] = True\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        def get_factor_list(num):\n",
    "            res = []\n",
    "            i = 2\n",
    "            while num > 1:\n",
    "                if num % i == 0:\n",
    "                    res.append(i)\n",
    "                    num //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            return res\n",
    "\n",
    "        res = set()\n",
    "        for num in nums:\n",
    "            res = res | set(get_factor_list(num))\n",
    "        \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "      prime = set()\n",
    "      def is_prime(n):\n",
    "        for i in range(2, int(n ** 0.5) + 1):\n",
    "          if n % i == 0:\n",
    "            return False\n",
    "        return True\n",
    "      \n",
    "      for num in nums:\n",
    "        if num < 4 or is_prime(num):\n",
    "          prime.add(num)\n",
    "        for i in range(2, int(num ** 0.5) + 1):\n",
    "          if num % i == 0:\n",
    "            if is_prime(num // i):\n",
    "              prime.add(num // i)\n",
    "            if is_prime(i):\n",
    "              prime.add(i)\n",
    "      return len(prime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        MAXN = 1000 + 1\n",
    "        prime = [False] * MAXN\n",
    "        visit = [False] * MAXN\n",
    "        for x in nums:\n",
    "            if visit[x]:\n",
    "                continue\n",
    "            visit[x] = True\n",
    "            i = 2\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    prime[i] = True\n",
    "                    x //= i\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                prime[x] = True\n",
    "        ans = sum(prime)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = []\n",
    "is_primes = [True] * 1001\n",
    "for x in range(2,1001):\n",
    "    if is_primes[x]:\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if p * x > 1000: break\n",
    "        is_primes[p*x] = False\n",
    "        if x % p == 0: break\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        nums = set(nums)\n",
    "        for x in nums:\n",
    "            for p in primes:\n",
    "                if x % p != 0: continue\n",
    "                s.add(p)\n",
    "                while x % p == 0: x //= p\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "\n",
    "pt=PrimeTable(1005)\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        v=set()\n",
    "        for x in nums:\n",
    "            for p,c in pt.prime_factorization(x):\n",
    "                v.add(p)\n",
    "        return len(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, N):\n",
    "        self.N = N + 1\n",
    "        self.F = list(range(self.N))\n",
    "        self.primes = []\n",
    "        for i in range(2, N + 1):\n",
    "            if self.F[i] == i:\n",
    "                for j in range(i, self.N, i):\n",
    "                    self.F[j] = i\n",
    "                self.primes.append(i)\n",
    "\n",
    "\n",
    "Pt = PrimeTable(1000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        S = set()\n",
    "        d = set(nums)\n",
    "        primes = Pt.primes\n",
    "        r = 0\n",
    "        for p in primes:\n",
    "            if p > 1000:\n",
    "                break\n",
    "            for n in d:\n",
    "                if n % p == 0:\n",
    "                    r += 1\n",
    "                    break\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_prime_factors(self, n):\n",
    "        i = 2\n",
    "        prime_factors = set()\n",
    "        while i * i <= n:\n",
    "            if n % i:\n",
    "                i += 1\n",
    "            else:\n",
    "                n //= i\n",
    "                prime_factors.add(i)\n",
    "        if n > 1:\n",
    "            prime_factors.add(n)\n",
    "        return prime_factors\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for num in nums:\n",
    "            ans = ans.union(self.get_prime_factors(num))\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        prime = []\n",
    "        mark = [False] * 1000\n",
    "        for i in range(2, 1000):\n",
    "            if not mark[i]:\n",
    "                prime.append(i)\n",
    "                j = i\n",
    "                while j * i < 1000:\n",
    "                    mark[j * i] = True\n",
    "                    j += 1\n",
    "        \n",
    "        result = set()\n",
    "        for n in nums:\n",
    "            p = 0\n",
    "            while n != 1:\n",
    "                find = False\n",
    "                while n % prime[p] == 0:\n",
    "                    n //= prime[p]\n",
    "                    find = True\n",
    "                if find:\n",
    "                    result.add(prime[p])\n",
    "                p += 1\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 3\n",
    "primes = []\n",
    "mark = [True for _ in range(N + 1)]\n",
    "for x in range(2, 1001):\n",
    "    if mark[x] == True:\n",
    "        primes.append(x)\n",
    "    for j in range(len(primes)):\n",
    "        if x * primes[j] > N:\n",
    "            break\n",
    "        mark[x * primes[j]] = False\n",
    "        if x % primes[j] == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:        \n",
    "        vis = set()\n",
    "        for num in nums:\n",
    "            for x in primes:\n",
    "                if x > num:\n",
    "                    break\n",
    "                if num % x == 0:\n",
    "                    vis.add(x)\n",
    "                \n",
    "        res = len(vis)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def get_prime_factors(n: int) -> list:\n",
    "    factors, i = [], 2\n",
    "    while i ** 2 <= n:\n",
    "        if n % i: i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i)\n",
    "    if n > 1: factors.append(n)\n",
    "    return factors\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            factors = get_prime_factors(x) # 包含重复元素\n",
    "            s |= set(factors)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, \n",
    "181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, \n",
    "547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, \n",
    "941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "        ans = set()\n",
    "        for x in nums:\n",
    "            for y in p:\n",
    "                if x % y == 0:\n",
    "                    ans.add(y)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumberTheoryPrimeFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil\n",
    "        self.prime_factor = [[] for _ in range(self.ceil + 1)]\n",
    "        self.min_prime = [0] * (self.ceil + 1)\n",
    "        self.get_min_prime_and_prime_factor()\n",
    "        return\n",
    "\n",
    "    def get_min_prime_and_prime_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            if not self.min_prime[i]:\n",
    "                self.min_prime[i] = i\n",
    "                for j in range(i * i, self.ceil + 1, i):\n",
    "                    if not self.min_prime[j]:\n",
    "                        self.min_prime[j] = i\n",
    "\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）\n",
    "        for num in range(2, self.ceil + 1):\n",
    "            i = num\n",
    "            while num > 1:\n",
    "                p = self.min_prime[num]\n",
    "                cnt = 0\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "                    cnt += 1\n",
    "                self.prime_factor[i].append([p, cnt])\n",
    "        return\n",
    "    \n",
    "\n",
    "nt = NumberTheoryPrimeFactor(1001)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        dct = set()\n",
    "        for num in nums:\n",
    "            for p, _ in nt.prime_factor[num]:\n",
    "                dct.add(p)\n",
    "        return len(dct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        def primefj(n):\n",
    "            factors = set()\n",
    "            i = 2\n",
    "            while i*i <= n:\n",
    "                if n%i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.add(i)\n",
    "            if n > 1:\n",
    "                factors.add(n)\n",
    "            return factors\n",
    "        print(primefj(100))\n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            s = primefj(num)\n",
    "            print(s)\n",
    "            for j in s:\n",
    "                a.add(j)\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        visited_num = defaultdict(int)\n",
    "        def divide(num):\n",
    "            for i in range(2, num):\n",
    "                if num % i == 0:\n",
    "                    if i in visited_num:\n",
    "                        left = visited_num[i]\n",
    "                    else:\n",
    "                        left = divide(i)\n",
    "                        visited_num[i] = left\n",
    "                    \n",
    "                    if num // i in visited_num:\n",
    "                        right = visited_num[num // i] \n",
    "                    else:\n",
    "                        right = divide(num // i)\n",
    "                        visited_num[num // i] = right\n",
    "                    return left + right\n",
    "            return [num]\n",
    "        \n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            a.update(divide(num))\n",
    "        return len(a)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        pVal = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\n",
    "                101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,\n",
    "                211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,\n",
    "                353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,\n",
    "                503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,\n",
    "                653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,\n",
    "                809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,\n",
    "                953,967,971,977,983,991,997]\n",
    "        lp = len(pVal)\n",
    "        def dfs(aV):\n",
    "            fp = bisect.bisect_left(pVal, aV)\n",
    "            if fp < lp and aV == pVal[fp]:\n",
    "                return [aV]\n",
    "            else:\n",
    "                p = 0\n",
    "                e = (aV + 1) // 2\n",
    "                while pVal[p] < e:\n",
    "                    if 0 == aV % pVal[p]:\n",
    "                        break\n",
    "                    else:\n",
    "                        p += 1\n",
    "                return [pVal[p]] + dfs(aV // pVal[p])\n",
    "             \n",
    "        s = set()\n",
    "        for n in nums:\n",
    "           s = s | set(dfs(n))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        lst=[]\n",
    "        for num in nums:\n",
    "            while num>1:\n",
    "                for j in range(2,num+1):\n",
    "                    c=0\n",
    "                    if num%j==0:\n",
    "                        num=num//j\n",
    "                        lst.append(j)\n",
    "                        c+=1\n",
    "                        break\n",
    "                if c==0:\n",
    "                    lst.append(num)\n",
    "                    num=1\n",
    "        return len(set(lst))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def get_prime_factors(n: int) -> list:\n",
    "    factors, i = [], 2\n",
    "    while i ** 2 <= n:\n",
    "        if n % i: i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i)\n",
    "    if n > 1: factors.append(n)\n",
    "    return factors\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            s |= set(get_prime_factors(x))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        nums_res = 1 # 乘积\n",
    "        for num in nums:\n",
    "            nums_res *= num\n",
    "        \n",
    "        factors = [] # 乘积的质因数\n",
    "\n",
    "        i = 2\n",
    "        while i * i <= nums_res: # 可能的质数，从 2 开始\n",
    "            if nums_res % i != 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                nums_res //= i\n",
    "                factors.append(i)\n",
    "        \n",
    "        if nums_res > 1:\n",
    "            factors.append(nums_res)\n",
    "        \n",
    "        factors_set = set(factors)\n",
    "        \n",
    "        res = len(factors_set)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        visited_num = defaultdict(int)\n",
    "        def divide(num):\n",
    "            for i in range(2, num):\n",
    "                if num % i == 0:\n",
    "                    if i in visited_num:\n",
    "                        left = visited_num[i]\n",
    "                    else:\n",
    "                        left = divide(i)\n",
    "                        visited_num[i] = left\n",
    "                    \n",
    "                    if num // i in visited_num:\n",
    "                        right = visited_num[num // i] \n",
    "                    else:\n",
    "                        right = divide(num // i)\n",
    "                        visited_num[num // i] = right\n",
    "                    return left + right\n",
    "            return [num]\n",
    "        \n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            a.update(divide(num))\n",
    "        return len(a)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        visited_num = defaultdict(int)\n",
    "        def divide(num):\n",
    "            for i in range(2, num):\n",
    "                if num % i == 0:\n",
    "                    if i in visited_num:\n",
    "                        left = visited_num[i]\n",
    "                    else:\n",
    "                        left = divide(i)\n",
    "                        visited_num[i] = left\n",
    "                    \n",
    "                    if num // i in visited_num:\n",
    "                        right = visited_num[num // i] \n",
    "                    else:\n",
    "                        right = divide(num // i)\n",
    "                        visited_num[num // i] = right\n",
    "                    return left + right\n",
    "            return [num]\n",
    "        \n",
    "        a = set()\n",
    "        for num in nums:\n",
    "            a.update(divide(num))\n",
    "        return len(a)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        lst=[]\n",
    "        for num in nums:\n",
    "            while num>1:\n",
    "                for j in range(2,num+1):\n",
    "                    c=0\n",
    "                    if num%j==0:\n",
    "                        num=num//j\n",
    "                        lst.append(j)\n",
    "                        c+=1\n",
    "                        break\n",
    "                if c==0:\n",
    "                    lst.append(num)\n",
    "                    num=1\n",
    "        return len(set(lst))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumberTheoryPrimeFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.prime_factor = [[] for _ in range(self.ceil + 1)]\n",
    "        self.min_prime = [0] * (self.ceil + 1)\n",
    "        self.get_min_prime_and_prime_factor()\n",
    "        return\n",
    "\n",
    "    def get_min_prime_and_prime_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            if not self.min_prime[i]:\n",
    "                self.min_prime[i] = i\n",
    "                for j in range(i * i, self.ceil + 1, i):\n",
    "                    if not self.min_prime[j]:\n",
    "                        self.min_prime[j] = i\n",
    "\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）\n",
    "        for num in range(2, self.ceil + 1):\n",
    "            i = num\n",
    "            while num > 1:\n",
    "                p = self.min_prime[num]\n",
    "                cnt = 0\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "                    cnt += 1\n",
    "                self.prime_factor[i].append([p, cnt])\n",
    "        return\n",
    "\n",
    "    def comb(self, n, m):\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(1, n+1):  # n!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] += y\n",
    "        for i in range(1, m+1):  # m!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "        for i in range(1, n-m+1):  # (n-m)!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "\n",
    "        ans = 1\n",
    "        for w in cnt:\n",
    "            ans *= w**cnt[w]\n",
    "        return ans\n",
    "\n",
    "\n",
    "nt = NumberTheoryPrimeFactor(1000+1)\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for num in nums:\n",
    "            for p, _ in nt.prime_factor[num]:\n",
    "                ans.add(p)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctPrimeFactors(self, nums: List[int]) -> int:\n",
    "        lst=[]\n",
    "        for num in nums:\n",
    "            while num>1:\n",
    "                for j in range(2,num+1):\n",
    "                    c=0\n",
    "                    if num%j==0:\n",
    "                        num=num//j\n",
    "                        lst.append(j)\n",
    "                        c+=1\n",
    "                        break\n",
    "                if c==0:\n",
    "                    lst.append(num)\n",
    "                    num=1\n",
    "        return len(set(lst))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
